DROPS

Document

DOI: 10.4230/LIPIcs.AofA.2020.5

The k-Cut Model in Conditioned Galton-Watson Trees

Authors: Gabriel Berzunza, Xing Shi Cai, and Cecilia Holmgren

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)

Abstract

The k-cut number of rooted graphs was introduced by Cai et al. [Cai and Holmgren, 2019] as a generalization of the classical cutting model by Meir and Moon [Meir and Moon, 1970]. In this paper, we show that all moments of the k-cut number of conditioned Galton-Watson trees converge after proper rescaling, which implies convergence in distribution to the same limit law regardless of the offspring distribution of the trees. This extends the result of Janson [Janson, 2006].

Cite as

Gabriel Berzunza, Xing Shi Cai, and Cecilia Holmgren. The k-Cut Model in Conditioned Galton-Watson Trees. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 5:1-5:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{berzunza_et_al:LIPIcs.AofA.2020.5,
  author =	{Berzunza, Gabriel and Cai, Xing Shi and Holmgren, Cecilia},
  title =	{{The k-Cut Model in Conditioned Galton-Watson Trees}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{5:1--5:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-147-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{159},
  editor =	{Drmota, Michael and Heuberger, Clemens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.5},
  URN =		{urn:nbn:de:0030-drops-120352},
  doi =		{10.4230/LIPIcs.AofA.2020.5},
  annote =	{Keywords: k-cut, cutting, conditioned Galton-Watson trees}
}

Document

DOI: 10.4230/LIPIcs.AofA.2020.6

Largest Clusters for Supercritical Percolation on Split Trees

Authors: Gabriel Berzunza and Cecilia Holmgren

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)

Abstract

We consider the model of random trees introduced by Devroye [Devroye, 1999], the so-called random split trees. The model encompasses many important randomized algorithms and data structures. We then perform supercritical Bernoulli bond-percolation on those trees and obtain a precise weak limit theorem for the sizes of the largest clusters. The approach we develop may be useful for studying percolation on other classes of trees with logarithmic height, for instance, we have also studied the case of complete d-regular trees.

Cite as

Gabriel Berzunza and Cecilia Holmgren. Largest Clusters for Supercritical Percolation on Split Trees. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 6:1-6:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{berzunza_et_al:LIPIcs.AofA.2020.6,
  author =	{Berzunza, Gabriel and Holmgren, Cecilia},
  title =	{{Largest Clusters for Supercritical Percolation on Split Trees}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{6:1--6:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-147-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{159},
  editor =	{Drmota, Michael and Heuberger, Clemens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.6},
  URN =		{urn:nbn:de:0030-drops-120361},
  doi =		{10.4230/LIPIcs.AofA.2020.6},
  annote =	{Keywords: Split trees, random trees, supercritical bond-percolation, cluster size, Poisson measures}
}

Search Results

Documents authored by Berzunza, Gabriel

The k-Cut Model in Conditioned Galton-Watson Trees

Abstract

Cite as

Largest Clusters for Supercritical Percolation on Split Trees

Abstract

Cite as

Thanks for your feedback!

Could not send message